package leetcode_bin_tree_test;

import bin_tree.TreeNode;

/**
 * 671. 二叉树中第二小的节点
 */
public class FindSecondMinimumValue {
    int first;
    public int findSecondMinimumValue(TreeNode root) {
        if (root.left == null) {
            // 说明这个二叉树只有一个根节点
            return -1;
        }
        this.first = root.val;
        return findTwo(root);
    }
    // 寻找下一个刚好小于first的数
    public int findTwo(TreeNode root) {
        if (root.val > first) {
            return root.val;
        }
        int left = -1, right = -1;
        if (root.left != null) {
            left = findTwo(root.left);
            right = findTwo(root.right);
        }
        return left == -1 || right == -1 ? Math.max(left, right) : Math.min(left, right);
    }
}

class Test {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        TreeNode n1 = new TreeNode(2);
        TreeNode n2 = new TreeNode(5);
        TreeNode n3 = new TreeNode(5);
        TreeNode n4 = new TreeNode(7);
        root.left = n1;
        root.right = n2;
        n2.left = n3;
        n2.right = n4;
        System.out.println(new FindSecondMinimumValue().findSecondMinimumValue(root));
    }
}
